<head>
    <meta charset="UTF-8">
<title>算法提高 Island Hopping</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<p class="MsoNormal" style="text-indent:21.0pt"><span style="font-family:宋体;
mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri">太平洋岛网公司（</span><span lang="EN-US">PLN</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;
mso-hansi-font-family:Calibri">）已经瞄向了太平洋中的一些群岛。这些群岛没有快捷的互联网连接。</span><span lang="EN-US">PLN</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;
mso-hansi-font-family:Calibri">计划向群岛提供互联网服务，以开发这个太平洋中潜在的市场。每组群岛的核心岛屿已经被深海电缆连入互联网。接下来需要做的事把其余岛屿和核心岛屿连接起来。</span> <span lang="EN-US"><o:p></o:p></span></p>
<p class="MsoNormal" style="text-indent:21.0pt"><span style="font-family:宋体;
mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri">对于每个岛，将给出它的路由器的位置和居民数量。</span><span lang="EN-US">PIN</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;
mso-hansi-font-family:Calibri">将会在群岛中连接多条电缆，每条电缆连接两座岛的路由器，最后使得每座岛都通过一条电缆路径与核心岛屿相连。</span><span lang="EN-US">PIN</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;
mso-hansi-font-family:Calibri">希望总的电缆长度最小。这样也许会有多个最佳方案。</span><span lang="EN-US">PIN</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri">并不关心哪个最佳网络方案被采纳。</span><span lang="EN-US"> <o:p></o:p></span></p>
<p class="MsoNormal" style="text-indent:21.0pt"><span lang="EN-US">PIN</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri">对于新顾客连上互联网的平均时间很感兴趣，我们不妨假设：所有连接网络的电线都是同时开始建设的。电缆铺设效率为一千米每天。因此，短的电缆会比长的更快铺好。</span><span lang="EN-US"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:Calibri;
mso-hansi-font-family:Calibri">当一座岛到核心岛屿的电缆连通时，这座岛就接入了互联网。</span><span lang="EN-US">PIN</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;
mso-hansi-font-family:Calibri">希望你告诉他所有居民连入互联网的平均时间。</span> <span lang="EN-US"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">&nbsp;</span>【输入格式】</p>
<p class="MsoNormal" style="text-indent:21.0pt"><span style="font-family:宋体;
mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri">输入数据包含多组群岛的描述。每组描述的第一行是一个正整数</span><span lang="EN-US">n</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;
mso-hansi-font-family:Calibri">，表示群岛的数量</span><span lang="EN-US">(n </span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri">&le;</span><span lang="EN-US"> 50)</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;
mso-hansi-font-family:Calibri">。接下来</span><span lang="EN-US">n</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri">行每行包含三个整数</span><span lang="EN-US">xi,yi,mi</span><span style="font-family:宋体;mso-ascii-font-family:
Calibri;mso-hansi-font-family:Calibri">，表示路由器的位置（</span><span lang="EN-US">xi,yi</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri">），以及岛上居民数量</span><span lang="EN-US">mi (mi &gt; 0)</span><span style="font-family:宋体;mso-ascii-font-family:
Calibri;mso-hansi-font-family:Calibri">。坐标以千米为单位。序列中的第一座岛是核心岛屿。</span><span lang="EN-US"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:Calibri;
mso-hansi-font-family:Calibri">输入数据最后以一个整数</span><span lang="EN-US">0</span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri">结束。</span></p>
<p>【输出格式】&nbsp;</p>
<p class="MsoNormal" style="text-indent:21.0pt"><span style="font-family:宋体;
mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri">对于测试点中的每组群岛，输出该组的序列号和居民连入互联网的平均天数。保留两位小数。具体</span><span lang="EN-US"> &nbsp; </span><span style="font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri">格式如样例输出所示。</span><span lang="EN-US"> <o:p></o:p></span></p>
<p><span style="font-size:10.5pt;mso-bidi-font-size:11.0pt;font-family:宋体;
mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri;mso-bidi-font-family:
&quot;Times New Roman&quot;;mso-font-kerning:1.0pt;mso-ansi-language:EN-US;mso-fareast-language:
ZH-CN;mso-bidi-language:AR-SA">每一个测试点输出后打印一个空行。</span><!--EndFragment-->&nbsp;</p>
<p>【样例输入】</p>
<p class="MsoNormal"><span lang="EN-US">7 <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">11 12 2500 <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">14 17 1500 <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">9 9 750 <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">7 15 600 <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">19 16 500 <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">8 18 400 <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">15 21 250 <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">0 <o:p></o:p></span></p>
<p><br />
【样例输出】</p>
<p class="MsoNormal"><span lang="EN-US">Island Group: 1&nbsp; Average 3.20<o:p></o:p></span></p>
<p><br />
【数据规模和约定】<br />
<span style="font-size:10.5pt;mso-bidi-font-size:11.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri;
mso-bidi-font-family:&quot;Times New Roman&quot;;mso-font-kerning:1.0pt;mso-ansi-language:
EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">输入数据中所有数字保证不超过</span><span lang="EN-US" style="font-size:10.5pt;mso-bidi-font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;
mso-fareast-font-family:宋体;mso-bidi-font-family:&quot;Times New Roman&quot;;mso-font-kerning:
1.0pt;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:
AR-SA">2^31-1</span><!--EndFragment-->&nbsp;</p>